package hero.mps.leet_code_16;

import java.util.Arrays;

public class Sum3Closest {
    public static int threeSumClosest(int[] nums, int target) {
        // 对数组进行排序
        Arrays.sort(nums);
        int n = nums.length;
        // 初始化最接近目标值的三数之和
        int closetSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1, right = n - 1;
            // 使用双指针法在已排序的数组中查找最接近目标值的三数之和
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                // 如果当前和与目标值的差的绝对值比之前找到的最接近值更小，则更新最接近值
                if (Math.abs(sum - target) < Math.abs(closetSum - target)) {
                    closetSum = sum;
                }
                // 如果当前和等于目标值，则返回该和
                if (sum == target) {
                    return sum;
                // 如果当前和小于目标值，则将左指针右移
                } else if (sum < target) {
                    left++;
                // 如果当前和大于目标值，则将右指针左移
                }else {
                    right--;
                }
            }
        }
        // 返回最接近目标值的三数之和
        return closetSum;

    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        System.out.println(threeSumClosest(nums, 1));
    }
}
